1809E - Two Tanks - CodeForces Solution

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <time.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <deque>
#include <ctype.h>
#include <limits.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <random>
#include <list>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const double PI = acos(-1.0);
const char* YES = "Yes";
const char* NO = "No";

void solve();
mt19937 rng(time(0));

// jiangly's modint template

template<class T>
constexpr T power(T a, ll b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(ll _x) : x{norm(_x % getMod())} {}
    
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int _x) const {
        if (_x < 0) {
            _x += getMod();
        }
        if (_x >= getMod()) {
            _x -= getMod();
        }
        return _x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        ll v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

// 注意：组合数必须 mod = 质数 且 n, k < mod 时才可用
template<int M>
class Comb {
    vector<int> Facs, Invs;
    void expand(size_t n) {
        while(Facs.size() < n + 1) Facs.push_back(1ll * Facs.back() * Facs.size() % M);
        if(Invs.size() < n + 1) { // 线性求阶乘的逆元
            Invs.resize(n + 1, 0);
            Invs.back() = 1;
            for(int a = Facs[n], p = M - 2; p; p >>= 1, a = 1ll * a * a % M)
                if(p & 1) Invs.back() = 1ll * Invs.back() * a % M; // 快速乘求 n! 的逆元
            for(int j = n-1; !Invs[j]; --j) Invs[j] = 1ll * Invs[j+1] * (j + 1) % M;
        }
    }
public:
    Comb() : Facs({1}), Invs({1}) {}
    Comb(int n) : Facs({1}), Invs({1}) { expand(n); }
    int operator() (int n, int k) {
        if(k > n) return 0;
        expand(n);
        return (1ll * Facs[n] * Invs[n-k] % M) * Invs[k] % M; 
    }
};

void get_factors(ll x, vector<int>& v) {
  for(int i = 2; i * i <= x; ++i) {
    if(x % i == 0) {
      v.push_back(i);
      if(i * i != x) {
        v.push_back(x / i);
      }
    }
  }
  v.push_back(x);
}

void get_primefactors(ll x, vector<int>& v) {
  int t = x;
  for(int i = 2; i * i <= x; ++i) {
    if(t % i == 0) {
      v.push_back(i);
      while(t % i == 0) {
        t /= i;
      }
    }
  }
  if(t != 1) {
    v.push_back(t);
  }
}

void init()
{
#ifdef _LOCAL_
  if (!freopen("case.txt", "r", stdin))
  {
    perror("open file failed!:");
    exit(1);
  }
  // if (!freopen("main.ans", "w", stdout))
  // {
  //   perror("open file failed!:");
  //   exit(1);
  // }
#endif
}
#ifdef _LOCAL_
void dbg_out()
{
  cerr << endl;
}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
  cerr << ' ' << H;
  dbg_out(T...);
}
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

ll read()
{
  int ch = getchar();
  if (ch == EOF)
  {
    return INT_MIN;
  }
  while (!isdigit(ch) && ch != '-')
  {
    ch = getchar();
    if (ch == EOF)
    {
      return INT_MIN;
    }
  }
  ll res = 0, sign = 1;
  if (ch == '-')
  {
    ch = getchar();
    sign = -1;
  }
  while (isdigit(ch))
  {
    res = res * 10 + ch - '0';
    ch = getchar();
  }
  return res * sign;
}

int nextchar()
{
  int ch = getchar();
  while (ch == ' ' || ch == '\n' || ch == '\r')
  {
    ch = getchar();
  }
  return ch;
}

void _print(bool x) {x? printf("Yes") : printf("No");}
void _print(double x) {printf("%.12lf", x);}
void _print(char x) { putchar(x);}
void _print(int x) { printf("%d", x);}
void _print(long x) { printf("%ld", x);}
void _print(unsigned long x) { printf("%lu", x);}
void _print(ll x) { 
#ifdef _LOCAL_
  printf("%I64d", x);
#else
  printf("%lld", x);
#endif
}
void _print(ull x) { 
#ifdef _LOCAL_
  printf("%I64u", x);
#else
  printf("%llu", x);
#endif
}
void _print(unsigned int x) { printf("%u", x);}
void _print(const char* s) { printf("%s", s);}
void _print(string& s) {printf("%s", s.c_str());}
template<typename T> void _print(vector<T>& v) {
  for(int i = 0; i < (int)v.size(); ++i) {
    _print(v[i]);
    if(i + 1 < (int)v.size()) {
      putchar(' ');
    }
  }
}
template<int N> void _print(MInt<N> x) { printf("%d", x.val());}

template<typename T1, typename T2> void _print(pair<T1, T2>& p) {
  _print(p.first);
  putchar(' ');
  _print(p.second);
}


void out() {}
template<typename Head, typename... Args> void out(Head val, Args... rem) {
  _print(val);
  if(sizeof...(rem) > 0) {
    putchar(' ');
  }
  out(rem...);
}

template<typename... Args> void outl(Args... args) {
  out(args...);
  out('\n');
}

template<typename... Args> void outs(Args... args) {
  out(args...);
  out(' ');
}

int main()
{
  init();
  solve();
  return 0;
}
/** 写之前 : 
 *  1. MAXN 是否定义正确？
 *  2. 要把所有数据读完后再计算!
 */
/*********************code start here*********************/
// 常用 2 的倍数
// 1 << 10 = 1024 --- 10^3
// 1 << 17 = 131072 --- 10^5
// 1 << 18 = 262144 --- 2 * 10^5
// 1 << 20 = 1048576 --- 10^6

/** 提交前检查项汇总
 1. 记忆化搜索：不要更改函数 f(x, y, ...) 里的参数 x,y 否则可能会无限递归
    建议采取定义新的变量的方式
 2. 数据范围是否是 10^10? 中间结果是否达到 10^10 - 10^18?
 3. 答案 res 和中间过程 是不是 ll!
 4. 不要用 multiset::count!
 5. 注意，用 map 做计数器时，[] 操作可能导致 size() 增加！
 6. 注意除零异常（造成 crash 的元凶之一）
*/

int res[1005][1005];
void solve() {
  int n = read(), a = read(), b = read();
  int v[n], s[n];
  for(int i = 0; i < n; ++i) {
    v[i] = read();
  }
  s[0] = v[0];
  for(int i = 1; i < n; ++i) {
    s[i] = s[i-1] + v[i];
  }
  int mx = 0, mn = 0;
  for(int i = 1; i < n; ++i) {
    if(s[i] > s[mx]) {
      mx = i;
    }
    if(s[i] < s[mn]) {
      mn = i;
    }
  }
  vector<int> dv[a + b + 1];
  for(int cd = 0; cd <= a + b; ++cd) {
    dv[min(a, cd) - max(0, cd - b)].push_back(cd);
  }
  for(int dif = 0; dif <= a + b; ++dif) {
    if(dv[dif].size()) {
      int x_mx = dif, i = mx + 1;
      while(i < n) {
        x_mx += v[i];
        x_mx = max(x_mx, 0);
        x_mx = min(x_mx, dif);
        i++;
      }
      int x_mn = 0;
      i = mn + 1;
      while(i < n) {
        x_mn += v[i];
        x_mn = max(x_mn, 0);
        x_mn = min(x_mn, dif);
        i++;
      }
      for(int cd : dv[dif]) {
        for(int cur = 0, c = min(a, cd), d = cd - c; cur <= dif; ++cur, --c, ++d) {
          int curres;
          if(cur + s[mx] >= dif) {
            curres = x_mx;
          } else if(cur + s[mn] <= 0) {
            curres = x_mn;
          } else {
            curres = cur + s[n-1];
          }
          res[c][d] = min(a, cd) - curres;
        }
      }
    }
  }
  for(int c = 0; c <= a; ++c) {
    for(int d = 0; d <= b; ++d) {
      outs(res[c][d]);
    }
    outl();
  }
}